﻿#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
    // 1005. K 次取反后最大化的数组和
    int largestSumAfterKNegations(vector<int>& nums, int k)
    {
        int ret = 0, mini = 0x3f3f3f3f, minus = 0;
        for (auto x : nums)
        {
            if (x < 0)
                ++minus;
            mini = min(mini, abs(x));
        }

        if (minus > k)
        {
            sort(nums.begin(), nums.end());
            for (int i = 0; i < k; ++i)
                ret += abs(nums[i]);
            for (int i = k; i < nums.size(); ++i)
                ret += nums[i];
        }
        else if (minus == k)
        {
            for (auto x : nums)
                ret += abs(x);
        }
        else
        {
            for (auto x : nums)
                ret += abs(x);
            if ((k - minus) % 2 != 0)
                ret -= 2 * mini;
        }
        return ret;
    }

    // 2418. 按身高排序
    vector<string> sortPeople(vector<string>& names, vector<int>& heights)
    {
        int n = names.size();
        vector<int> index;
        for (int i = 0; i < n; ++i)
            index.push_back(i);
        sort(index.begin(), index.end(), [&heights](const int i, const int j)
            {
                return heights[i] > heights[j];
            });
        vector<string> ret;
        for (int i = 0; i < n; ++i)
            ret.push_back(names[index[i]]);
        return ret;
    }
};

int main()
{
    /*vector<int> v{ 4,2,3 };
    cout << Solution().largestSumAfterKNegations(v, 1) << endl;*/

    vector<string> names{ "Mary","John","Emma" };
    vector<int> heights{ 180,165,170 };
    Solution().sortPeople(names, heights);

    return 0;
}